class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #动态规划，k为除i，j外最后一个被戳破的气球
        #dp[i, j] = dp[i, k] + nums[i] * nums[k] * nums[j] + dp[k, j]
        #dp[i, j]表示i,j间最大的金币数，开区间
        #前后各增加一个1
        def get_coins(dp, nums, i, j):
            max_coin = 0
            for k in range(i+1, j):
               left = dp[i][k]
               right = dp[k][j]
               coin = left + right + nums[i] * nums[k] * nums[j] 
               max_coin = max(max_coin, coin)
            return max_coin

        nums.insert(0, 1)
        nums.append(1)
        dp = [[0 for i in range(len(nums))] for i in range(len(nums))]

        for n in range(2, len(nums)):
            for i in range(0, len(nums) - n):
                j = i + n
                dp[i][j] = get_coins(dp, nums, i, j)
        return dp[0][len(nums) - 1]
